This application is directed to methods and apparatus for data hiding in an image and, more particularly, to lossless and reversible data hiding in the spatial domain.
In the field of data hiding, pieces of information represented by the data are hidden in the cover media (e.g., a pixel image). In other words, the data hiding process links two sets of data, a set of the embedded data and another set of the cover media data. The relationship between these two sets of data defines different applications. For instance in covert communications, the hidden data are irrelevant to the cover media. In authentication, however, the embedded data are closely related to the cover media. In these types of applications, invisibility of hidden data is an important requirement. In most cases, the cover media will experience some distortion due to data hiding and cannot be inverted back to the original media. Indeed, some permanent distortion occurs to the cover media even after the hidden data have been extracted.
In some applications, such as medical diagnosis and law enforcement, it is desirable to reverse the marked media back to the original cover media after the hidden data are retrieved for consideration. The marking techniques satisfying this requirement are referred to as reversible, lossless, distortion-free, or invertible data hiding techniques. Reversible data hiding links two sets of data in such a way that the cover media can be losslessly recovered after the hidden data have been extracted. This provides an additional avenue of handling the two different sets of data.
Many of the existing data hiding techniques are not reversible. For instance, widely utilized spread-spectrum based data hiding methods have been disclosed in the following publications: J. Cox, J. Kilian, T. Leighton, and T. Shamoon, “Secure Spread Spectrum Watermarking for Multimedia,” IEEE Trans. on Image Processing, Vol. 6, No. 12, pp. 1673-1687 (December 1997); and J. Huang and Y. Q. Shi, “An Adaptive Image Watermarking Scheme Based on Visual Masking,” Electronics letters, 34(8): 748-750 (1998). These techniques, however, are not invertible owing to truncation (for the purpose to prevent over/underflow) error, and round-off error.
Another well-known least significant bit-plane (LSB) approach is discussed in J. Irvine and D. Harle, Data Communications and Networks: An Engineering Approach, West Sussex, England: John Wiley & Sons, Ltd. (2002). This approach is not lossless owing to bit-replacement without “memory.”
Another category of data hiding techniques is quantization-index-modulation (QIM), which is discussed in detail in B. Chen and G. W. Wornell, “Quantization Index Modulation: A Class of Provably Good Methods for Digital Watermarking and Information Embedding,” IEEE Transactions on Information Theory, Vol. 47, No. 4, pp. 1423-1443 (May 2001). This technique is not distortion-free owing to the quantization error.
Although most of the current digital watermarking algorithms are not lossless, some recent marking techniques have been reported as being lossless. For example, two methods carried out in the image spatial domain purport to be lossless. The details of these methods may be found in U.S. Pat. No. 6,278,791 (the entire disclosure of which is hereby incorporated by reference) and J. Fridrich, M. Goljan and R. Du, “Invertible Authentication,” Proc. SPIE, Security and Watermarking of Multimedia Contents, pp. 197-208, San Jose, Calif., (January. 2001). In the '791 patent, the marking is carried out in the spatial domain. The method uses modulo 256 addition to embed a hash value of an original image for authentication. The technique is reversible because of the modulo 256 addition; however, the modulo 256 addition also may produce some annoying salt-and-pepper noise due to grayscale flipping over between 0 and 255 in either direction. The Fridrich approach also operates in the spatial domain and losslessly compresses some selected bit-plane(s) to leave space for data embedding. Since bookkeeping data are also embedded as overhead, the method is reversible. The amount of hidden data, however, is quite limited because the bias between binary bits, 0s and 1s (the tendecy the have more 0's or more 1's in the data) is not significant in the several lower levels that include the least significant bit-plane (LSB) in the spatial domain. The lack of bias was probably not a problem in the Fridrich approach because it is directed towards data authentication instead of data embedding.
A purportedly lossless marking technique has also been developed in the transform domain, as is discussed in detail in B. Macq and F. Deweyand, “Trusted Headers For Medical Images,” DFG VIII-D II Watermarking Workshop, Erlangen, Germany, (October. 1999). This reversible marking technique was developed in the transform domain and is based on a lossless multi-resolution transform and the patchwork theory. It also uses modulo 256 addition. Since each block, say, an 8×8 block can only be used to embed one bit, the amount of hidden data that may be achieved is quite limited. More details concerning the patchwork theory may be found in W. Bender, D. Gruhl, N. Morimoto and A. Lu, “Techniques for Data Hiding,” IBM Systems Journal, Vol. 35, No. 3-4, pp. 313-336 (1996).
Yet another marking technique is discussed in detail in C. De Vleeschouwer, J. F. Delaigle and B. Macq, “Circular Interpretation on Histogram for Reversible Watermarking,” IEEE International Multimedia Signal Processing Workshop, France, pp. 345-350 (October 2001). The capacity of this method, which is based on the idea of patchwork and modulo 256 addition, is also limited except that it is expected to exhibit some robustness against high quality JPEG compression.
A reversible marking technique that is suitable for a large amount of hidden data is discussed in detail in M. Goljan, J. Fridrich, and R. Du, “Distortion-free Data Embedding,” Proceedings of 4th Information Hiding Workshop, pp. 27-41, Pittsburgh, Pa., (April 2001), also in U.S. patent application Ser. No.: 2003/0081809 (the entire disclosure of which is hereby incorporated by reference). The amount of hidden data achievable by this technique, however, is still not large enough for many applications, such as medical applications. Indeed, the pay-load ranges from 3,000 bits to 24,000 bits for a 512×512×8 grayscale image, i.e., from 0.011 bits per pixel (bpp) to 0.092 bpp as the PSNR of the marked image versus the original image is 39 dB. This technique first segments an image into non-overlapped blocks, and then introduces a discriminating function to classify these blocks into three groups: R(egular), S(ingular) and U(nusable). It further introduces a flipping operation, which can convert an R block to an S block and vice versa. A U block remains intact after the flipping operation. By assigning, say, a binary 1 to an R block and a binary 0 to an S block, all R and S blocks are scanned in a chosen sequential order, resulting in a binary sequence. This binary sequence is losslessly compressed and the compressed sequence is saved as overhead for late reconstruction of the original image. In data embedding, the R and S blocks are scanned once again and the flipping operation is applied whenever necessary to make the changed R and S block sequence coincident with the to-be-embedded data (another binary 0 and 1 bit stream) followed by the overhead data. While successful in reversible data hiding, the payload is still not large enough for some applications, as indicated above. Another problem with the method is that when the embedding strength increases in order to increase payload, the visual quality drops severely due to annoying artifacts.
To increase payload dramatically, a new lossless data hiding technique based on integer wavelet transform is discussed in detail in U.S. patent application Ser. No.: 60/527,900, filed Dec. 5, 2003, entitled Methods and Apparatus for Lossless Data Hiding, the entire disclosure of which is hereby incorporated by reference. Because of the superior decorrelation capability of the wavelet transform, the selected bit-plane compression in high frequency subbands creates more space for data hiding, resulting in a higher payload than that in the method described in U.S. patent application Ser. No.: 2003/0081809. Specifically, for a 512×512×8 image, 5,000 bits to 80,000 bits can be embedded, i.e., the payload is from 0.019 bpp to 0.31 bpp while the PSNR of the marked image versus the original image is guaranteed above 48 dB. In addition, the integer wavelet transform, a second generation wavelet transform, helps to avoid round-off error. To achieve reversible data hiding, a histogram modification is applied during pre-processing to prevent over/underflow. This histogram modification causes, however, a lower PSNR of the marked image versus the original image though there are no annoying artifacts.
It is noted that reversible data hiding has attracted more and more attention recently and more and more algorithms are being developed. Another example is the technique reported in M. U. Celik, G. Sharma, A. M. Tekalp and E. Saber, “Reversible Data Hiding,” Proceedings of IEEE 2002 International Conference on Image Processing, Vol. 2, pp. 157-160 (September 2002). Still a further example is the technique reported in J. Tian, “Reversible Data Embedding Using a Difference Expansion,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 8, pp. 890-896, August 2003.
Accordingly, there are needs in the art for new methods and apparatus for achieving lossless marking that can embed a relatively large amount of data, while keeping a high visual quality of the marked images.